|
| creator |
Lohrey, Markus
| | Kuske, Dietrich
| | date |
2005-09-28
| | | | description |
22 pages
| |
The logic L(Q_u) extends first-order logic by a generalized form of
counting quantifiers ("the number of elements satisfying ...
belongs to the set C"). This logic is investigated for
structures with an injective omega-automatic presentation. If
first-order logic is extended by an infinity-quantifier, the
resulting theory of any such structure is known to be decidable
(Blumensath, Grädel 2004). It is shown that, as in the case of
automatic structures (Khoussainov, Rubin, Stephan 2004) also
modulo-counting quantifiers as well as infinite cardinality
quantifiers ("there are c many elements satisfying ...")
lead to decidable theories. For a structure of bounded degree with
injective omega-automatic presentation, the fragment of L(Q_u) that
contains only effective quantifiers is shown to be decidable and an
elementary algorithm for this decision is presented. Both
assumptions (omega-automaticity and bounded degree) are necessary
for this result to hold.
| | format |
application/pdf
| | 265092 Bytes | |